#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

struct Edge {
    int dest;
    int weight;
};

class AdjacencyList {
private:
    int numVertices;
    vector<vector<Edge>> adjacencyList;
    vector<bool> visited;//(numVertices, false);  // 记录顶点是否被访问过

public:
    AdjacencyList(int numVertices) : numVertices(numVertices) {
        adjacencyList.resize(numVertices);//有多少个顶点，那么存顶点的容器就创建多大
        visited.resize(numVertices, false);
    }

    void addEdge(int src, int dest, int weight) {
        Edge edge;
        edge.dest = dest;
        edge.weight = weight;
        adjacencyList[src].push_back(edge);
        // 对称位置也添加边，如果是有向图，将下面两行注释掉
        edge.dest = src;
        adjacencyList[dest].push_back(edge);
    }

    void printGraph() {
        for (int i = 0; i < numVertices; ++i) {
            cout << "Vertex " << i << " --> ";
            for (const Edge& edge : adjacencyList[i]) {
                cout << "(" << edge.dest << ", " << edge.weight << ") ";
            }
            cout << endl;
        }
    }
    vector<vector<Edge>> convertToInverseAdjacencyList() {
        vector<vector<Edge>> inverseAdjacencyList(numVertices);
        for (int src = 0; src < numVertices; ++src) {
            for (const Edge& edge : adjacencyList[src]) {//将这个点指向的点一个个找到
                Edge edge1;
                edge1.dest = src;//指向它的点的号码
                edge1.weight = edge.weight;//权重
                inverseAdjacencyList[edge.dest].push_back(edge1);//将被指向点放入指向它的点以及权重
                //edge.dest就代表0这个点所指向的点1
            }
        }
        return inverseAdjacencyList;
    }
    void DFS(int startVertex) {
        vector<bool> visited(numVertices, false);  // 记录顶点是否被访问过
        stack<int> stack;  // 使用栈来实现DFS
        // 将起始顶点入栈并标记为已访问
        stack.push(startVertex);
        visited[startVertex] = true;
        while (!stack.empty()) {
            int currentVertex = stack.top();
            stack.pop();
            cout << currentVertex << " ";  // 输出当前访问的顶点
            // 遍历当前顶点的邻接顶点
            for (const Edge& edge : adjacencyList[currentVertex]) {//遍历该节点指向的节点
                if (!visited[edge.dest]) {//如果该节点没有被遍历过
                    stack.push(edge.dest);//入栈
                    visited[edge.dest] = true;//标记
                }
            }
        }
        cout<<endl;
    }
    void BFS(int startVertex){
        cout<<"{ ";
        //vector<bool> visited(numVertices, false);  // 记录顶点是否被访问过
        queue<int> queue;//用队列去模仿BFS
        //将起始节点加入队列并标记已经访问
        queue.push(startVertex);
        visited[startVertex] = true;
        while(!queue.empty()){
            int currentVertex = queue.front();
            queue.pop();
            cout<< currentVertex <<" ";//输出当前访问节点
            for(const Edge& edge : adjacencyList[currentVertex]){//遍历该节点指向的节点
                if(!visited[edge.dest]){//如果该节点没有被遍历过
                    queue.push(edge.dest);
                    visited[edge.dest] = true;
                }
            }
        }
        cout<<"}"<<endl;

        for(int i=0;i<numVertices;i++){
            if(!visited[i]){
                BFS(i);
            }
        }
    }
    // 查找顶点的根节点
    int findRoot(vector<int>& parent, int v) {
        if (parent[v] == v)
            return v;
        return findRoot(parent, parent[v]);
    }
    // 合并两个集合
    void unionSets(vector<int>& parent, int v1, int v2) {
        int root1 = findRoot(parent, v1);
        int root2 = findRoot(parent, v2);
        parent[root2] = root1;
    }

};